package org.opencv.samples.tutorial3;

import java.util.ArrayList;

import android.util.Log;

public class VirtualMap {

	// PRIVATE MEMBERS
	private final int MAX_MARKERS = 138;
	private ArrayList<Integer> pathSeq = new ArrayList<Integer>( );
	private static Graph infoBuilding;

//	privateivate ArrayList<Integer> answer = new ArrayList<Integer>( );

	/**
	 * CONSTRUCTOR for this class
	 */
	public VirtualMap( )
	{
		infoBuilding = new Graph(MAX_MARKERS);
		
		// Add all markers
		setMarkers(infoBuilding);
	}

	/**
	 * 
	 * @param startMarker
	 * @param destMarker
	 * @return
	 */
	public ArrayList<Integer> getShortestPath(int startVertex, int destVertex)
	{
//		startVertex = 0;
//		destVertex = destVertex;
		
		Log.i("GRAPH MESSAGE", "src: " + infoBuilding.getVertex(startVertex) + " dest: " + infoBuilding.getVertex(destVertex));
		
//		if (answer.size( ) > 0) { answer = null; }
		ArrayList<Integer> answer = dijkstraAlgorithm(infoBuilding, startVertex, destVertex);
		
		for (int i = answer.size( ) - 1; i >= 0; --i)
		{
			// Copy the result as a reverse order
			pathSeq.add(answer.get(i));
		}
		

		// Return the result
		return pathSeq;

//		// First check if the vertices are valid
//		if (checkValidInput(infoBuilding, startMarker, destMarker))
//		{
//			// Find the corresponding vertex in the graph 
//			int startVertex = findCorrVertex(infoBuilding, startMarker);
//			int destVertex = findCorrVertex(infoBuilding, destMarker);
//
//			// Get the shortest path using dijkstra algorithm
//			ArrayList<Integer> answer = dijkstraAlgorithm(infoBuilding, startVertex, destVertex);
//
//			for (int i = answer.size( ) - 1; i >= 0; --i)
//			{
//				// Copy the result as a reverse order
//				pathSeq.add(answer.get(i));
//			}
//		}
//		else
//		{
//			Log.i("GRAPH MESSAGE", "INPUTED MARKERS ARE NOT VALID... SORRY!!");
//			return null;
//			//			System.exit(0);
//		}
//
//		// Return the result
//		return pathSeq;
		//return (ArrayList<Integer>) pathSeq.clone( );
	}

	/**
	 * Dijkstra algorithm to get shortest path from one marker to another
	 * @param g
	 * @param startVertex
	 * @param destVertex
	 * @return
	 */
	private static ArrayList<Integer> dijkstraAlgorithm(Graph g, int startVertex, int destVertex)
	{
		boolean[ ] allowedVertices = new boolean[g.size( )];
		int[ ] distance = new int[g.size( )];
		int[ ] predecessor = new int[g.size( )];

		int allowedSize;
		int sum, next = 0;
		int n, v = 0;
		int smallest;

		ArrayList<Integer> answer = new ArrayList<Integer>( );

		// Initialize the distance array to contain all INFINITY except distance[start], which is set to zero.
		// Initialize the set of allowed vertices to be the empty set.
		for (int i = 0; i < g.size( ); ++i) 
		{
			distance[i] = Graph.INFINITY;
			allowedVertices[i] = false;
		}
		distance[startVertex] = 0;

		// Compute the complete distance array
		n = g.size( );
		for (allowedSize = 1; allowedSize < n; ++allowedSize) // why 1? we don't need to care the start vertex
		{
			// At this point, allowedVertices contains allowedSize - 1 vertices, which are the
			// allowedSize - 1 closet vertices to the start vertex. Also, for each vertex v, distance[v]
			// is the shortest distance from the start vertex to vertex v, provided that we are
			// considering only permitted paths (i.e., parths where each vertex except the final vertex
			// must be in allowedVertices).

			// Let next be the closest vertex to the start vertex, which is not yet in the set of
			// allowed vertices (if several verticies are equally close, then you may choose next to be any of them.
			smallest = Graph.INFINITY;
			for (v = 0; v < n; ++v)
			{
				if ((!allowedVertices[v]) && (distance[v] <= smallest))
				{
					smallest = distance[v];
					next = v;
				}
			}

			// Add the vertex next to the set allowed_vertices.
			allowedVertices[next] = true;

			// Revise the distance array so that the new vertex (next) may appear on permitted paths.
			for (v = 0; v < n; ++v)
			{
				sum = distance[next] + g.getEdge(next, v);
				if (sum < distance[v])
				{
					distance[v] = sum;
					predecessor[v] = next;
				}
			}
		}

		// Printing the vertices on the shortest path from the start vertex to v:
		// Vertices are printed in reverse order, starting at v, and going to start	
		int vertexOnPath = destVertex; // The last vertex on the path
		answer.add(vertexOnPath);
		while (vertexOnPath != startVertex)
		{
			vertexOnPath = predecessor[vertexOnPath];
			answer.add(vertexOnPath);
		}

		return answer;
//		return (ArrayList<Integer>) answer.clone( );
	}

	/**
	 * 
	 * @param g
	 * @param start
	 * @return
	 */
	public int findCorrVertex(String start)
	{
		int answer = -1;

		for (int i = 0; i < infoBuilding.size(); ++i)
		{
			if (infoBuilding.getVertex(i).equals(start))
			{
				answer = i;
				break;
			}
			
		}
		

		return answer;
	}

//	/**
//	 * 
//	 * @param g
//	 * @param src
//	 * @param dest
//	 * @return
//	 */
//	private static boolean checkValidInput(Graph g, String src, String dest)
//	{
//		boolean srcValid = false;
//		boolean destValid = false;
//
//		for (int i = 0; i < g.size( ); ++i)
//		{
//			if (g.getVertex(i).equals(src))
//				srcValid = true;
//
//			if (g.getVertex(i).equals(dest))
//				destValid = true;
//
//			if (srcValid && destValid) { break; }
//		}
//
//		return (srcValid == destValid);
//	}
	

	public String getSrcToDest(int v1, int v2)
	{
		String answer = "";
		
		answer = (String) infoBuilding.getVertex(v1);
		answer = answer.concat("to");
		answer = answer.concat((String)infoBuilding.getVertex(v2));

		return answer;
	}
	
	/**
	 * 
	 * @param g
	 */
	private static void setMarkers(Graph g)
	{
		//
		// Vertices(markers) and Edges in 2F
		g.setVertex(0, "DUMMY");
		g.setVertex(1, "M202");
		g.setVertex(2, "M203");
		g.setVertex(3, "M204");
		g.setVertex(4, "M205");
		g.setVertex(5, "IM2_1");
		g.setVertex(6, "IM2_2");
		g.setVertex(7, "IM2_3");
		g.setVertex(8, "SM2_1");
		g.setVertex(9, "SM2_2");

		//g.addEdge(0, 1, 2); // from 201 to 202
		g.addEdge(1, 5, 1); // from 202 to IM2_1
		g.addEdge(5, 2, 1); // from IM2_1 to 203
		g.addEdge(2, 3, 2); // from 203 to 204
		g.addEdge(5, 6, 1); // from IM2_1 to IM2_2
		g.addEdge(6, 7, 1); // from IM2_2 to IM2_3
		g.addEdge(6, 8, 1); // from IM2_2 to SM2_1
		g.addEdge(7, 4, 2); // from IM2_3 to 205
		g.addEdge(8, 9, 1); // from SM2_1 to SM2_2

		//
		// Vertices(markers) and Edges in 3F
		g.setVertex(10, "M301");
		g.setVertex(11, "M302");
		g.setVertex(12, "M303");
		g.setVertex(13, "M304");
		g.setVertex(14, "M305");
		g.setVertex(15, "M321");
		g.setVertex(16, "M323");
		g.setVertex(17, "M325");
		g.setVertex(18, "M327");
		g.setVertex(19, "IM3_1");
		g.setVertex(20, "IM3_2");
		g.setVertex(21, "IM3_3");
		g.setVertex(22, "IM3_4");
		g.setVertex(23, "SM3_1");
		g.setVertex(24, "SM3_2");

		g.addEdge(9, 21, 1); // from 2F to 3F
		g.addEdge(10, 11, 2); // from 301 to 302
		g.addEdge(11, 19, 1); // from 302 to IM3_1
		g.addEdge(19, 12, 1); // from IM3_1 to 303
		g.addEdge(12, 13, 2); // from 303 to 304
		g.addEdge(19, 20, 1); // from IM3_1 to IM3_2
		g.addEdge(20, 21, 1); // from IM3_2 to IM3_3
		g.addEdge(20, 23, 1); // from IM3_2 to SM3_1
		g.addEdge(21, 14, 2); // from IM3_3 to 305
		g.addEdge(23, 24, 1); // from SM3_1 to SM

		g.addEdge(14, 22, 3); // from 305 to IM3_4
		g.addEdge(22, 15, 1); // from IM3_4 to 321
		g.addEdge(15, 16, 2); // from 321 to 323
		g.addEdge(16, 17, 2); // from 323 to 325
		g.addEdge(17, 18, 2); // from 325 to 327

		//
		// Vertices(markers) and Edges in 4F
		g.setVertex(25, "M401");
		g.setVertex(26, "M402");
		g.setVertex(27, "M403");
		g.setVertex(28, "M405");
		g.setVertex(29, "M406");
		g.setVertex(30, "M407");
		g.setVertex(31, "M409");
		g.setVertex(32, "M421");
		g.setVertex(33, "M424");
		g.setVertex(34, "M429");
		g.setVertex(35, "IM4_1");
		g.setVertex(36, "IM4_2");
		g.setVertex(37, "IM4_3");
		g.setVertex(38, "IM4_4");
		g.setVertex(39, "IM4_5");
		
		
		g.setVertex(40, "M201");
		g.addEdge(40, 1, 2);
		
//		for (int i = 41; i < 137; ++i)
//		{
//			if (i == 66) { continue; }
//			g.setVertex(i, "TEMP_M" + i);
//		}
//		
//		g.setVertex(137, "TM1");
//		g.setVertex(66, "TM2");
//		g.addEdge(137, 66, 1); // from 137 to 66 is connected
		
		g.addEdge(24, 36, 1); // from 3F to 4F
		g.addEdge(25, 26, 2); // from 401 to 402
		g.addEdge(26, 27, 2); // from 402 to 403
		g.addEdge(27, 35, 1); // from 403 to IM4_1
		g.addEdge(35, 28, 1); // from IM4_1 to 405
		g.addEdge(28, 29, 2); // from 405 to 406
		g.addEdge(35, 30, 1); // from IM4_1 to 407
		g.addEdge(30, 36, 1); // from 407 to IM4_2
		g.addEdge(36, 31, 1); // from IM4_2 to 409
		g.addEdge(31, 37, 3); // from 409 to IM4_3
		g.addEdge(37, 38, 1); // from IM4_3 to IM4_4
		g.addEdge(38, 39, 1); // from IM4_4 to IM4_5
		g.addEdge(39, 32, 1); // from IM4_5 to 421
		g.addEdge(32, 33, 2); // from 421 to 424
		g.addEdge(33, 34, 2); // from 424 to 429
	}

}
